package two_pointer.leetcode_941_easy;

/**
 * 判断一个数组是否是有效的山脉数组
 * 给定一个整数数组 A，如果它是有效的山脉数组就返回 true，否则返回 false。
 *
 * 让我们回顾一下，如果 A 满足下述条件，那么它是一个山脉数组：
 *
 *      1. A.length >= 3
 *      2.在 0 < i < A.length - 1 条件下，存在 i 使得：
 *          A[0] < A[1] < ... A[i-1] < A[i]
 *          A[i] > A[i+1] > ... > A[A.length - 1]
 *
 */
public class ValidMountainArray {
    /**
     * 双指针，分别从左右向中间遍历数组，如果最后两个指针在同一个位置，则是有效的山脉数组
     * @param A 给定数组
     * @return  false：该数组不是一个有效山脉数组 / ture：该数组是一个有效山脉数组
     */
    public boolean validMountainArray(int[] A) {
        if (A == null || A.length < 3){
            return false;
        }
        int len = A.length;
        int left = 0;
        int right = A.length - 1;
        /**
         * 特殊情况：
         *      一个递增数组，则right位置将会保持不变，最终left = right
         *      一个递减数组，则left 位置将会保持不变，最终left = right
         *
         *      两种情况都不是有效的山脉数组。
         *
         *      且不能越界
         */
        while(left + 1 < A.length && A[left + 1] > A[left]){
            left++;
        }
        while(right - 1 >= 0 && A[right - 1] > A[right]){
            right--;
        }
        return left != 0 && right != len - 1 && left == right;
    }
}
